1. Field of the Invention
The present invention is directed toward the field of computers and electronic design automation, and more particularly towards storing representations of polygons for computer and electronic design automation applications.
2. Art Background
Many applications today analyze multidimensional data records. A multidimensional data record contains a number of data values, which are defined along a number of dimensions (also called attributes or keys) in a multidimensional space. Such records are typically stored in data files or databases.
A spatial data record is one type of multidimensional data record. Spatial data records typically describe the attributes (e.g., the position, size, shape, etc.) of geometric objects, such as points, lines, polygons, regions, surfaces, volumes, etc. Spatial records are used in many fields, including computer-aided design, computer graphics, data management systems, robotics, image processing, geographic information systems, pattern recognition, and computational geometry.
Effective data structures are needed to organize multidimensional and spatial data records efficiently, in order to optimize the time for querying these records. For instance, a sequential list of the multidimensional data records provides the simplest way of storing the records. However, the time needed for performing a query on such a list is intolerably high in most cases since each record in the list needs to be examined for each query. Numerous multidimensional data structures have been proposed for organizing multidimensional and spatial data records. Hanan Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley Publishing, 1990, includes a review of many of these data structures.
Multidimensional data structures include hierarchical data structures. Hierarchical structures are based on the principle of recursive decomposition of the data space (i.e., the object space or the image space). In other words, these data structures are created by recursively dividing the data space, and storing the data records according to their location in the divided space. Quadtrees and k-d trees are two types of hierarchical data structures.
Electronic design automation (xe2x80x9cEDAxe2x80x9d) applications assist engineers in designing integrated circuits (xe2x80x9cIC""sxe2x80x9d). Specifically, these applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. These layouts are formed by geometric shapes that represent layers of different materials and devices on IC""s. Spatial data records define the spatial attributes of many of these geometric shapes. For instance, spatial data records are used to define geometric shapes that represent conductive interconnect lines. Interconnect lines route signals on the IC""s. These lines are sometimes referred to as wire segments or segs. EDA applications typically characterize interconnect lines as rectangles. The rectangles depict interconnect lines deposed on the IC in a vertical and/or horizontal directions, relative to the boundaries of the integrated circuit. As described fully below, the present invention characterizes interconnect lines as polygons. The polygons depict interconnect lines deposed on the IC in diagonal directions, relative to the boundaries of the integrated circuit. Thus, it is desireable to create mechanisms to manipulate and store polygons in a multi-dimensional space.
Geometric objects, such as polygons, are defined in a multi-dimensional data space. The geometric objects are represented by data segments for processing in a computer. xe2x80x9cNxe2x80x9d dimensional hierarchical trees, or xe2x80x9cngxe2x80x9d trees, are generated to organize the data segments into xe2x80x9coutside child nodesxe2x80x9d and xe2x80x9cinside child nodesxe2x80x9d in accordance with a discriminator value. The discriminator value is selected for each layer or discriminator dimension in the ng tree. For the ng tree, one of xe2x80x9cnxe2x80x9d sides of a polygon is selected as the discriminator value. To create the ng tree, data segments are designated as xe2x80x9coutside child nodesxe2x80x9d if a data segment is outside the plane defined by the discriminator value, and data segments are selected as xe2x80x9cinside child nodesxe2x80x9d if the data segment is inside the plane defined by the discriminator value. This process of partitioning data segments into inside child nodes and outside child nodes is repeated recursively through each level of the ng tree.